1. Field of the Invention
The present invention relates to a method for cache management of track removal in a cache for a storage.
2. Description of the Related Art
A cache management system buffers tracks in a storage device recently accessed as a result of read and write operations in a faster access storage device, such as memory, than the storage device storing the requested tracks. Subsequent read requests to tracks in the faster access cache memory are returned at a faster rate than returning the requested tracks from the slower access storage, thus reducing read latency. The cache management system may also return complete to a write request when the modified track directed to the storage device is written to the cache memory and before the modified track is written out to the storage device, such as a hard disk drive. The write latency to the storage device is typically significantly longer than the latency to write to a cache memory. Thus, using cache also reduces write latency.
A cache management system may maintain a linked list having one entry for each track stored in the cache, which may comprise write data buffered in cache before writing to the storage device, or read data. In the commonly used Least Recently Used (LRU) cache technique, if a track in the cache is accessed, i.e., a cache “hit”, then the entry in the LRU list for the accessed track is moved by a cache manager to a Most Recently Used (MRU) end of the list. If the requested track is not in the cache, i.e., a cache miss, then the track in the cache whose entry is at the LRU end of the list may be removed.
One removal operation, often referred to as demoting a track, simply deletes the track from cache. For example, a track containing read data may be demoted by a cache manager. Another track removal operation destages the track from cache for sending the track to storage. For example, a track containing write data may be destaged from cache by the cache manager for storing in storage.
In a typical LRU cache technique, an entry for a track data staged into cache from the storage is usually added to the MRU end of the LRU list. Consequently, tracks that are more frequently accessed are likely to remain in cache, while data less frequently accessed will more likely be removed from the LRU end of the list to make room in cache for newly accessed tracks.
The cache manager scans the list of tracks to identify tracks that can be demoted or destaged. The cache manager typically uses a “lock,” often referred to as an “LRU lock” to lock the list to prevent modification of the list by other processors while the scan is in progress. In many LRU cache techniques, the cache manager holds the LRU lock for the full duration of the scan. In addition, should a track be identified for removal from the cache, the cache manager typically continues to hold the LRU lock for the demotion or destaging process which is usually undertaken as the scan progresses.
The cache manager may hold the lock for other cache management operations. For example, after a track in cache has been accessed in a read or write operation, the cache manager typically holds the lock while the entry position for that track in the list is moved by the cache manager to the MRU end of the list.
The duration of time that the cache manager holds the lock, preventing access to the list by other processors, tends to be relatively long for list scanning and track removal operations. The duration of time that the cache manager holds the lock for a typical MRU operation tends to be relatively short but they can be relatively frequent in number.
Other techniques may also be used to manage track removal from a cache. For example, tracks which have been accessed may be marked as “accessed” using a recency bit.